import offer.TreeNode;
import sun.security.util.math.intpoly.P256OrderField;

import javax.sound.sampled.DataLine.Info;

/**
 * @Author: wangliuyang
 * @Date: 2021/8/13 22:43
 * @Description:124. 二叉树中的最大路径和
 */
public class Solution_124 {
    class Info {
        int fromHeadMaxSum;
        int allMaxSum;
        public Info(int fromHeadMaxSum,int allMaxSum){
            this.allMaxSum = allMaxSum;
            this.fromHeadMaxSum = fromHeadMaxSum;
        }
    }
    //和root有关：1、root 2、root+左子树fromheadMax 3、root+右子树fromheadmax 4、root + 左 + 右
    //和root无关：1、左边allmaxsum 2、右边allmaxsum
    public int maxPathSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Info info = this.getMaxPathSum(root);
        return info.allMaxSum;
    }

    private Info getMaxPathSum(TreeNode root) {
        if (root == null) {
            return  null;
        }
        Info leftInfo = getMaxPathSum(root.left);
        Info rightInfo = getMaxPathSum(root.right);
        int p1 = Integer.MIN_VALUE;
        if (leftInfo != null){
            p1 = leftInfo.allMaxSum;
        }
        int p2 = Integer.MIN_VALUE;
        if (rightInfo != null) {
            p2 = rightInfo.allMaxSum;
        }
        int p3 = root.val;
        int p4 = Integer.MIN_VALUE;
        if (leftInfo != null){
            p4 = leftInfo.fromHeadMaxSum + root.val;
        }
        int p5 = Integer.MIN_VALUE;
        if (rightInfo != null){
            p5 = rightInfo.fromHeadMaxSum + root.val;
        }
        int p6 = Integer.MIN_VALUE;
        if (rightInfo != null && leftInfo != null){
            p6 = leftInfo.fromHeadMaxSum + rightInfo.fromHeadMaxSum + root.val;
        }
        int allMaxSum = Math.max(Math.max(p5,p6),Math.max(Math.max(p1,p2),Math.max(p3,p4)));
        int fromHeadMaxSum = Math.max(p3,Math.max(p4,p5));
        return new Info(fromHeadMaxSum,allMaxSum);
    }
}
